package leetcode_600;

/**
 *@author 周杨
 *FriendCircles_547 一个二维数组 num[i][j]表示i和j是朋友 问有多少朋友圈
 *describe:AC 7%
 *2018年9月13日 上午10:36:43
 */
public class FriendCircles_547 {
	
	
	 /**
	 * describe:深度优先搜索 搜索过就标记 AC
	 * 2018年9月13日 上午10:36:24
	 */
	public int findCircleNum(int[][] M) {
	        int rows = M.length;
	        int cols = M[0].length;
	        boolean[][] visited = new boolean[rows][cols];
	        
	        int numCircles = 0;
	        for (int i = 0; i < M.length; i++) {
	            for (int j = 0; j < M[i].length; j++) {
	                if (! visited[i][j] && M[i][j] == 1) {
	                    DFS(M, i, j, visited);
	                    numCircles++;
	                }
	            }
	        }
	        return numCircles;
	    }
	    
	    //  traverse to the "end" of the circle, so that in the parent method, we don't hit repeats of a circle
	    public void DFS(int[][] M, int row, int col, boolean[][] visited) {
	        visited[row][col] = true;        
	        
	        for (int j = 0; j < M[row].length; j++) {
	            if (shouldVisit(M, col, j, visited)) {
	                DFS(M, col, j, visited);
	            }
	        }
	        
	    }
	    
	    public boolean shouldVisit(int[][] M, int row, int col, boolean[][] visited) {
	        return row >= 0 && row < M.length && col >= 0 && col < M[0].length && M[row][col] == 1 && !visited[row][col];
	    }
	
	
	/**
	 * describe:以为是孤岛问题 错误 题目没有看清楚。。。
	 * 2018年9月13日 上午10:25:54
	 */
	public int findCircleNum1(int[][] M) {
		if(M.length==0||M[0].length==0)
			return 0;
		int res=0;
        for(int i=0;i<M.length;++i)
        	for(int j=0;j<M[0].length;++j) {
        		if(M[i][j]==1) {
        			++res;
        			dfs(M,i,j);
        		}
        	}
        return res;
    }
	
	public void dfs(int [][]M,int x,int y) {
		if(x<0||y<0||x==M.length||y==M[0].length)
			return ;
		if(M[x][y]==1) {
			M[x][y]=2;
			dfs(M,x,y+1);
			dfs(M,x,y-1);
			dfs(M,x+1,y);
			dfs(M,x-1,y);
		}
	}
}
